package com.le.tester.imooc.oldfairy.coding.sorting;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * createTime：2023/5/24 14:49
 * description：桶序排序
 */
public class BucketSort {

    public List<Integer> sort(List<Integer> list) {


        //桶使用链表进行实现
        int k = 100;
        List<LinkedList<Integer>> linkedLists = new ArrayList<>();

        List<Integer> result = new ArrayList<>();
        //创建桶,只创建k个桶
        for (int i = 0; i < k; i++) {
            linkedLists.add(new LinkedList<>());
        }

        //桶的hash,这边使用模的形式进行
        for (Integer item : list) {
            //随机桶增加item
            linkedLists.get(item % k).add(item);
        }

        //桶打包
        for (LinkedList<Integer> item : linkedLists) {
            result.addAll(item);
        }

        return result;


    }

    public List<Integer> gen() {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 1000; i++) {
            list.add((int) (Math.random() * i));
        }
        return list;
    }

    @Test
    public void testBucketSort() {
        List<Integer> gen = this.gen();
        this.sort(gen);
    }
}
